package com.java.basis.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {5, 9, 7, 4, 1, 3, 2, 8};
//        int[] a = {1, 2, 3, 4, 5, 7, 8, 9};
//        bubble(a);
//        bubble2(a);
//        bubble3(a);
        bubble4(a);
    }

    /**
     * 最基础的冒泡排序，每轮都要比较length-1
     *
     */
    private static void bubble(int[] a) {
        for (int j = 0; j < a.length - 1; j++) {
            for (int i = 0; i < a.length - 1; i++) {
                System.out.println("比较次数" + (i+1));
                if (a[i] > a[i+1]) {
                    swap(a, i, i + 1);
                }
            }
            System.out.println("第"+ (j+1) +"轮冒泡输出 = " + Arrays.toString(a));
        }
    }

    /**
     * 优化一：
     * 因为每一轮比较都能确定最后一个最大的数字，所以之后每一轮的比较次数都减一
     *
     */
    private static void bubble2(int[] a) {
        for (int j = 0; j < a.length - 1; j++) {
            for (int i = 0; i < a.length - 1 - j; i++) {
                System.out.println("比较次数" + (i+1));
                if (a[i] > a[i+1]) {
                    swap(a, i, i + 1);
                }
            }
            System.out.println("第"+ (j+1) +"轮冒泡输出 = " + Arrays.toString(a));
        }
    }

    /**
     * 优化二：
     * 有时候会出现，已经拍好了顺序，还在进行比较，这是我们可以设置一个是否发生交换的标志
     * 当没有交换时，就说明数组已经有序了
     *
     */
    private static void bubble3(int[] a) {
        for (int j = 0; j < a.length - 1; j++) {
            boolean swaped = false;//是否发生交换
            for (int i = 0; i < a.length - 1 - j; i++) {
                System.out.println("比较次数" + (i+1));
                if (a[i] > a[i+1]) {
                    swap(a, i, i + 1);
                    swaped = true;
                }
            }
            System.out.println("第" + (j + 1) + "轮冒泡输出 = " + Arrays.toString(a));
            if(!swaped) {
                break;
            }
        }
    }

    /**
     * 优化四：
     * 有时候发现后面的有些已经有序了，还在进行比较，会比较浪费时间
     * 因此我们可以记录最后一次发生交换的下标，等到下次进行比较的时候，改下表之后的数据就不进行比较
     *
     */
    private static void bubble4(int[] a) {
        int n = a.length - 1;
        while(n != 0) {
            int last = 0;//表示最后一次减缓索引位置
            for (int i = 0; i < n; i++) {
                System.out.println("比较次数" + (i+1));
                if (a[i] > a[i+1]) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            System.out.println("每轮冒泡输出 = " + Arrays.toString(a));
            n = last;
        }
    }

    //数字交换
    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}
